#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		vector<TreeNode *> an_p = getAncestorList(root, p);
		vector<TreeNode *> an_q = getAncestorList(root, q);
		TreeNode *res=NULL;
		for (int i = 0; i < an_p.size(); i++) {
			TreeNode *common=an_p[i];
			for (int j = 0; j < an_q.size(); j++) {
				if (common->val == an_q[j]->val) {
					res = common;
					break;
				}
			}
			if (res) break;
		}
		return res;
	}

	vector<TreeNode*> getAncestorList(TreeNode *root, TreeNode *p) {
		vector<TreeNode*> list;
		list.push_back(p);
		TreeNode *r=p;
		while (r != root) {
			r = findParent(root, r);
			list.push_back(r);
		}
		return list;
	}

	TreeNode* findParent(TreeNode *root, TreeNode *p) {
		if (!root) return NULL;
		TreeNode *l, *r;
		if (root == p || root->left == p || root->right == p)
			return root;
		else {
			l=findParent(root->left, p);
			if (l) return l;
			r=findParent(root->right, p);
			return r;
		}
	}
};

void main() {
	Solution s;
	TreeNode root(3), n5(5), n1(1), n6(6), n2(2), n0(0), n8(8), n7(7), n4(4);
	root.left = &n5, root.right = &n1, n1.left = &n0, n1.right = &n8, n5.left = &n6, n5.right = &n2, n2.left = &n7, n2.right = &n4;
	s.lowestCommonAncestor(&root,&n4,&n0);
}